#include <iostream>
#include <queue>

using namespace std;

template<class T>
struct BinaryTreeNode
{
    T m_element;
    BinaryTreeNode<T>* leftChild;
    BinaryTreeNode<T>* rightChild;

    BinaryTreeNode(){leftChild = nullptr; rightChild = nullptr;}
    BinaryTreeNode(const T& element)
    {
        m_element = element;
        leftChild = nullptr;
        rightChild = nullptr;
    }
    BinaryTreeNode(const T& element, BinaryTreeNode* left,
                   BinaryTreeNode* right)
    {
        m_element = element;
        leftChild = left;
        rightChild = right;
    }

};

template<class T>
class BinaryTree
{
public:
    virtual ~BinaryTree(){}
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual void preOrder(void (*)(T*)) = 0;
    virtual void inOrder(void (*)(T*)) = 0;
    virtual void postOrder(void (*)(T*)) = 0;
    virtual void levelOrder(void (*)(T*)) = 0;
};

template<class T>
class LinkedBinaryTree : public BinaryTree<BinaryTreeNode<T>>
{
public:
    LinkedBinaryTree():m_root(nullptr), m_size(0){}
    ~LinkedBinaryTree(){erase();}
    bool empty()const{return m_size == 0;}

    int size()const{return m_size;}

    void preOrder(void (*theVisit)(BinaryTreeNode<T>* node))
    {visit = theVisit; preOrder(m_root);}

    void inOrder(void (*theVisit)(BinaryTreeNode<T>* node))
    {visit = theVisit; inOrder(m_root);}

    void postOrder(void (*theVisit)(BinaryTreeNode<T>* node))
    {visit = theVisit; postOrder(m_root);}

    void levelOrder(void (*theVisit)(BinaryTreeNode<T>* node))
    {visit = theVisit; levelOrder(m_root);}

    // 调用 void preOrder(void (*theVisit)(BinaryTreeNode<T>* node))
    void preOrderOutput(){preOrder(output); std::cout<<std::endl;}

    void inOrderOutput(){inOrder(output); std::cout<<std::endl;}

    void postOrderOutput(){postOrder(output); std::cout<<std::endl;}

    void levelOrderOutput(){levelOrder(output); std::cout<<std::endl;}

    void erase(){postOrder(dispose); m_root = nullptr; m_size = 0;}
private:
    int m_size;
    BinaryTreeNode<T> * m_root;
    static void (*visit)(BinaryTreeNode<T>*); // 函数指针

    static void preOrder(BinaryTreeNode<T>* node)
    {
        if(node != nullptr){
            visit(node);
            preOrder(node->leftChild);
            preOrder(node->rightChild);
        }
    }

    static void inOrder(BinaryTreeNode<T>* node)
    {
        if(node != nullptr){
            inOrder(node->leftChild);
            visit(node);
            inOrder(node->rightChild);
        }
    }

    static void postOrder(BinaryTreeNode<T>* node)
    {
        if(node != nullptr){
            postOrder(node->leftChild);
            postOrder(node->rightChild);
            visit(node);
        }
    }

    static void levelOrder(BinaryTreeNode<T>* node)
    {
        std::queue<T> t_queue;
        t_queue.push(node);

        while (!t_queue.empty()) {
            BinaryTreeNode<T>* t = t_queue.pop();
            if(t != nullptr){
                visit(t);
            }
            if(t->leftChild != nullptr){
                t_queue.push(t->leftChild);
            }
            if(t->rightChild != nullptr){
                t_queue.push(t->rightChild);
            }
        }
    }

    static void output(BinaryTreeNode<T>* node)
    {
        std::cout<<node->m_element<<" ";
    }

    int height(BinaryTreeNode<T>* node)
    {
        if(node == nullptr){
            return 0;
        }
        int h1 = height(node->leftChild); // 左树高
        int h2 = height(node->rightChild);// 右树高
        h1 = h1 > h2 ? h1 : h2;
        return ++h1;
    }

    static void dispose(BinaryTreeNode<T>* node){delete node;}
};


int main(int argc, char *argv[])
{
    std::cout<<"Hello binary tree."<<std::endl;
    return 0;
}













